package binary_tree

func MaxSubBst(root *Node) int {
	if root == nil {return 0}
	h := GetMaxSubBstSize(root)
	if h != 0 {
		return h
	}
	return max(MaxSubBst(root.Left), MaxSubBst(root.Right))
}

func GetMaxSubBstSize(node *Node) int {
	var ans []int
	fn := func(val int) {
		ans = append(ans, val)
	}
	inProcess(node, fn)
	for i:=1 ; i<len(ans); i++ {
		if ans[i] < ans[i-1] {
			return 0
		}
	}
	return len(ans)
}


type MaxSubBstInfo struct {
	isBst  bool
	max    int
	min    int
	size   int
}


func MaxSubBst2(root *Node) int {
	if root == nil {return 0}
	return MaxSubBstProcess(root).size
}

func MaxSubBstProcess (node *Node) *MaxSubBstInfo {
	if node == nil {
		return nil
	}
	leftInfo := MaxSubBstProcess(node.Left)
	rightInfo := MaxSubBstProcess(node.Right)

	maxV, minV := node.Val, node.Val
	if leftInfo != nil {
		minV = min(minV, leftInfo.min)
		maxV = max(maxV, leftInfo.max)
	}
	if rightInfo != nil {
		minV = min(minV, rightInfo.min)
		maxV = max(maxV, rightInfo.max)
	}

	isBst := true
	if leftInfo != nil && rightInfo != nil {
		isBst = leftInfo.isBst && rightInfo.isBst && leftInfo.max < node.Val && rightInfo.min > node.Val
	} else if leftInfo != nil && rightInfo == nil {
		isBst = leftInfo.isBst && leftInfo.max < node.Val
	} else if leftInfo == nil && rightInfo != nil {
		isBst = rightInfo.isBst && rightInfo.min > node.Val
	}

	size := 0
	if isBst {
		if leftInfo != nil && rightInfo != nil {
			size = leftInfo.size + rightInfo.size + 1
		} else if leftInfo != nil && rightInfo == nil {
			size = leftInfo.size + 1
		} else if leftInfo == nil && rightInfo != nil {
			size = rightInfo.size + 1
		} else {
			size = 1
		}
	} else {
		if leftInfo != nil && rightInfo != nil {
			size = max(leftInfo.size, rightInfo.size)
		} else if leftInfo != nil && rightInfo == nil {
			size = leftInfo.size
		} else if leftInfo == nil && rightInfo != nil {
			size = rightInfo.size
		}
	}
	return &MaxSubBstInfo{isBst, maxV, minV, size}
}
